package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName _216组合总和III
 * @Description TODO
 * @Author 昝亚杰
 * @Date 2021/10/8 20:50
 * Version 1.0
 **/
public class _216组合总和III {
    List<Integer> list = new ArrayList<>();
    ArrayList<List<Integer>> lists = new ArrayList<List<Integer>>();
    int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        getCombinationSum3(1,k,n);
        return lists;
    }
    public void  getCombinationSum3(int start, int k, int n){
        if(sum == n && list.size() == k){
            lists.add(new ArrayList<>(list));
            return ;
        }
        if(list.size() < k || sum < n){
            for(int i = start; i <= 9 - (k - list.size()) + 1; i++){
                list.add(i);
                sum = sum + i;
                getCombinationSum3(i + 1,k,n);
                list.remove(list.size() - 1);
                sum = sum - i;
            }
        }else{
            return ;
        }
    }
}
